package com.yanceysong.codetop.s1_s10;

import com.yanceysong.common.ListNode;
import com.yanceysong.common.util.NodePrintUtil;

/**
 * @ClassName Qusection206
 * @Description
 * @date 2024/6/5 下午3:22
 * @Author yanceysong
 * @Version 1.0
 */
public class S3_Easy_206_反转链表 {
    /**
     * 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
     * first    second
     * null  ->  1   ->  2    ->  3   ->  4(null)
     */
    public ListNode reverseList(ListNode head) {
        // 一开始双指针第一个在外面
        ListNode pre = null, current = head;
        while (current != null) {

            // 保留指针为了下一步的移动
            ListNode temp = current.next;
            // 转向
            current.next = pre;

            // 双指针移动
            pre = current;
            current = temp;
        }
        return pre;
    }

    public static void main(String[] args) {
        S3_Easy_206_反转链表 solution = new S3_Easy_206_反转链表();

        System.out.println("=== 反转链表测试开始 ===");

        // 测试1: 基本功能测试
        System.out.println("\n--- 测试1: 基本功能测试 ---");
        testBasicFunctionality(solution);

        // 测试2: 边界情况测试
        System.out.println("\n--- 测试2: 边界情况测试 ---");
        testBoundaryCases(solution);

        // 测试3: 不同长度链表测试
        System.out.println("\n--- 测试3: 不同长度链表测试 ---");
        testDifferentLengths(solution);

        // 测试4: 特殊值测试
        System.out.println("\n--- 测试4: 特殊值测试 ---");
        testSpecialValues(solution);

        // 测试5: 性能测试
        System.out.println("\n--- 测试5: 性能测试 ---");
        testPerformance(solution);

        // 额外验证：反转正确性
        verifyReverseCorrectness();

        System.out.println("\n=== 所有测试完成 ===");
    }

    /**
     * 创建链表的辅助方法
     *
     * @param values 节点值数组
     * @return 链表头节点
     */
    private static ListNode createList(int[] values) {
        if (values == null || values.length == 0) {
            return null;
        }

        ListNode head = new ListNode(values[0]);
        ListNode current = head;

        for (int i = 1; i < values.length; i++) {
            current.next = new ListNode(values[i]);
            current = current.next;
        }

        return head;
    }

    /**
     * 将链表转换为数组的辅助方法
     *
     * @param head 链表头节点
     * @return 节点值数组
     */
    private static int[] listToArray(ListNode head) {
        if (head == null) {
            return new int[0];
        }

        // 先计算链表长度
        int length = 0;
        ListNode current = head;
        while (current != null) {
            length++;
            current = current.next;
        }

        // 转换为数组
        int[] result = new int[length];
        current = head;
        for (int i = 0; i < length; i++) {
            result[i] = current.val;
            current = current.next;
        }

        return result;
    }

    /**
     * 打印数组的辅助方法
     */
    private static void printArray(int[] arr) {
        if (arr.length == 0) {
            System.out.print("[]");
            return;
        }

        System.out.print("[");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]);
            if (i < arr.length - 1) {
                System.out.print(", ");
            }
        }
        System.out.print("]");
    }

    /**
     * 测试基本功能
     */
    private static void testBasicFunctionality(S3_Easy_206_反转链表 solution) {
        // 测试1: 典型情况 [1,2,3,4,5] -> [5,4,3,2,1]
        int[] input1 = {1, 2, 3, 4, 5};
        int[] expected1 = {5, 4, 3, 2, 1};

        ListNode head1 = createList(input1);
        ListNode result1 = solution.reverseList(head1);
        int[] actual1 = listToArray(result1);

        System.out.print("输入: ");
        printArray(input1);
        System.out.print(" -> 输出: ");
        printArray(actual1);
        System.out.print(" (期望: ");
        printArray(expected1);
        System.out.println(")");

        assert java.util.Arrays.equals(actual1, expected1) : "基本功能测试1失败";

        // 测试2: 两个节点 [1,2] -> [2,1]
        int[] input2 = {1, 2};
        int[] expected2 = {2, 1};

        ListNode head2 = createList(input2);
        ListNode result2 = solution.reverseList(head2);
        int[] actual2 = listToArray(result2);

        System.out.print("输入: ");
        printArray(input2);
        System.out.print(" -> 输出: ");
        printArray(actual2);
        System.out.print(" (期望: ");
        printArray(expected2);
        System.out.println(")");

        assert java.util.Arrays.equals(actual2, expected2) : "基本功能测试2失败";

        System.out.println("✓ 基本功能测试通过");
    }

    /**
     * 测试边界情况
     */
    private static void testBoundaryCases(S3_Easy_206_反转链表 solution) {
        // 测试1: 空链表
        ListNode result1 = solution.reverseList(null);
        System.out.println("输入: null -> 输出: " + (result1 == null ? "null" : "非null") + " (期望: null)");
        assert result1 == null : "空链表测试失败";

        // 测试2: 单个节点 [1] -> [1]
        int[] input2 = {1};
        int[] expected2 = {1};

        ListNode head2 = createList(input2);
        ListNode result2 = solution.reverseList(head2);
        int[] actual2 = listToArray(result2);

        System.out.print("输入: ");
        printArray(input2);
        System.out.print(" -> 输出: ");
        printArray(actual2);
        System.out.print(" (期望: ");
        printArray(expected2);
        System.out.println(")");

        assert java.util.Arrays.equals(actual2, expected2) : "单个节点测试失败";

        System.out.println("✓ 边界情况测试通过");
    }

    /**
     * 测试不同长度的链表
     */
    private static void testDifferentLengths(S3_Easy_206_反转链表 solution) {
        // 测试1: 3个节点
        int[] input1 = {1, 2, 3};
        int[] expected1 = {3, 2, 1};
        testReverseCase(solution, input1, expected1, "3个节点");

        // 测试2: 4个节点
        int[] input2 = {1, 2, 3, 4};
        int[] expected2 = {4, 3, 2, 1};
        testReverseCase(solution, input2, expected2, "4个节点");

        // 测试3: 6个节点
        int[] input3 = {1, 2, 3, 4, 5, 6};
        int[] expected3 = {6, 5, 4, 3, 2, 1};
        testReverseCase(solution, input3, expected3, "6个节点");

        // 测试4: 10个节点
        int[] input4 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        int[] expected4 = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
        testReverseCase(solution, input4, expected4, "10个节点");

        System.out.println("✓ 不同长度链表测试通过");
    }

    /**
     * 测试特殊值
     */
    private static void testSpecialValues(S3_Easy_206_反转链表 solution) {
        // 测试1: 包含负数
        int[] input1 = {-1, 0, 1};
        int[] expected1 = {1, 0, -1};
        testReverseCase(solution, input1, expected1, "包含负数");

        // 测试2: 相同值
        int[] input2 = {1, 1, 1, 1};
        int[] expected2 = {1, 1, 1, 1};
        testReverseCase(solution, input2, expected2, "相同值");

        // 测试3: 大数值
        int[] input3 = {1000, 2000, 3000};
        int[] expected3 = {3000, 2000, 1000};
        testReverseCase(solution, input3, expected3, "大数值");

        // 测试4: 混合正负数
        int[] input4 = {-5, -1, 0, 3, 7};
        int[] expected4 = {7, 3, 0, -1, -5};
        testReverseCase(solution, input4, expected4, "混合正负数");

        System.out.println("✓ 特殊值测试通过");
    }

    /**
     * 辅助方法：测试反转情况
     */
    private static void testReverseCase(S3_Easy_206_反转链表 solution, int[] input, int[] expected, String description) {
        ListNode head = createList(input);
        ListNode result = solution.reverseList(head);
        int[] actual = listToArray(result);

        System.out.print(description + " - 输入: ");
        printArray(input);
        System.out.print(" -> 输出: ");
        printArray(actual);
        System.out.print(" (期望: ");
        printArray(expected);
        System.out.println(")");

        assert java.util.Arrays.equals(actual, expected) : description + "测试失败";
    }

    /**
     * 测试性能
     */
    private static void testPerformance(S3_Easy_206_反转链表 solution) {
        // 测试1: 中等长度链表 (1000个节点)
        System.out.println("性能测试1: 1000个节点");
        testPerformanceCase(solution, 1000);

        // 测试2: 较长链表 (10000个节点)
        System.out.println("性能测试2: 10000个节点");
        testPerformanceCase(solution, 10000);

        // 测试3: 长链表 (100000个节点)
        System.out.println("性能测试3: 100000个节点");
        testPerformanceCase(solution, 100000);

        System.out.println("✓ 性能测试通过");
    }

    /**
     * 辅助方法：性能测试用例
     */
    private static void testPerformanceCase(S3_Easy_206_反转链表 solution, int length) {
        // 创建长链表
        ListNode head = new ListNode(1);
        ListNode current = head;
        for (int i = 2; i <= length; i++) {
            current.next = new ListNode(i);
            current = current.next;
        }

        // 测试反转性能
        long startTime = System.currentTimeMillis();
        ListNode result = solution.reverseList(head);
        long endTime = System.currentTimeMillis();

        // 验证结果正确性（检查头尾节点）
        assert result.val == length : "性能测试：头节点值不正确";

        // 找到尾节点验证
        ListNode tail = result;
        while (tail.next != null) {
            tail = tail.next;
        }
        assert tail.val == 1 : "性能测试：尾节点值不正确";

        System.out.println("  长度: " + length + ", 执行时间: " + (endTime - startTime) + "ms");

        // 验证时间复杂度为O(n)，对于合理大小的输入应该很快完成
        assert (endTime - startTime) < 1000 : "性能测试：执行时间过长，可能存在性能问题";
    }

    /**
     * 额外的验证方法：验证反转的正确性
     */
    private static void verifyReverseCorrectness() {
        System.out.println("\n--- 额外验证：反转正确性 ---");
        S3_Easy_206_反转链表 solution = new S3_Easy_206_反转链表();

        // 创建测试链表 1->2->3->4->5
        ListNode head = createList(new int[]{1, 2, 3, 4, 5});

        System.out.println("原链表结构验证:");
        NodePrintUtil.printListNodeWithDescription(head, "原链表");
        // 反转链表
        ListNode reversed = solution.reverseList(head);

        System.out.println("反转后链表结构验证:");
        NodePrintUtil.printListNodeWithDescription(reversed, "反转链表");

        // 再次反转，应该恢复原状
        ListNode doubleReversed = solution.reverseList(reversed);

        System.out.println("二次反转链表结构验证:");
        NodePrintUtil.printListNodeWithDescription(doubleReversed, "二次反转链表\"");

        // 验证二次反转后是否恢复原状
        int[] original = {1, 2, 3, 4, 5};
        int[] doubleReversedArray = listToArray(doubleReversed);

        assert java.util.Arrays.equals(original, doubleReversedArray) : "二次反转验证失败";
        System.out.println("✓ 二次反转验证通过：链表恢复原状");
    }
}
